package leetcode.code0736;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	private final String LET = "let";
	private final String ADD = "add";
	private final boolean MULT = false;

	public int evaluate(String expression) {
		char[] exp = expression.toCharArray();
		Map<String, String> params = new HashMap<>();
		return Integer.valueOf(this.evaluate(exp, 1, exp.length - 2, params));
	}

	// exp，以params为参数，在L，R范围上计算结果
	private String evaluate(char[] exp, int L, int R, Map<String, String> params) {
		int p = L;
		while (exp[p] != ' ') {
			p++;
		}
		String op = new String(exp, L, p - L);
		L = p + 1;
		if (op.equals(this.LET)) {
			return this.let(exp, L, R, params);// 前缀操作LET
		} else if (op.equals(this.ADD)) {
			return this.op(exp, L, R, params, !MULT); // 前缀操作ADD
		} else {
			return this.op(exp, L, R, params, MULT); // 前缀操作MULT
		}
	}

	private String op(char[] exp, int L, int R, Map<String, String> params, boolean add) {
		int l = L, r = L;
		List<Integer> nums = new ArrayList<>();// 两个操作数
		while (r <= R) {
			String str = null;
			if (exp[r] != '(') {
				// 简单类型
				r = this.ends1(exp, r, R);
				str = new String(exp, l, r - l);
			} else {
				// 嵌套类型
				r = this.ends2(exp, r);// 配套括号
				str = this.evaluate(exp, l + 1, r - 1, new HashMap<>(params));
			}
			if (params.containsKey(str)) {
				// 来自之前的let赋值
				nums.add(Integer.valueOf(params.get(str)));
			} else {
				nums.add(Integer.valueOf(str));
			}
			r = r + 1;
			while (r <= R && exp[r] == ' ')
				r++;
			l = r;
		}
		// 加法还是乘法
		return add ? String.valueOf(nums.get(0) + nums.get(1)) : String.valueOf(nums.get(0) * nums.get(1));
	}

	private String let(char[] exp, int L, int R, Map<String, String> params) {
		int l = L, r = L;
		boolean isParam = true;
		String param = null;
		while (r <= R) {
			String str = null;
			if (exp[r] != '(') {
				r = this.ends1(exp, r, R);
				str = new String(exp, l, r - l);
			} else {
				r = this.ends2(exp, r);// 配套括号，获得括号尾部
				str = this.evaluate(exp, l + 1, r - 1, new HashMap<>(params));
			}
			if (isParam) {
				param = str;
			} else {
				str = params.containsKey(str) ? params.get(str) : str;
				params.put(param, str);
			}
			r = r + 1;
			while (r <= R && exp[r] == ' ')
				r++;
			l = r;
			isParam = !isParam;
		}
		return params.containsKey(param) ? params.get(param) : param;
	}

	private int ends1(char[] exp, int r, int R) {
		while (r <= R && exp[r] != ' ') {
			r++;
		}
		return r;
	}

	private int ends2(char[] exp, int r) {
		int cnt = 1;
		while (cnt != 0) {
			r++;
			if (exp[r] == '(') {
				cnt++;
			} else if (exp[r] == ')') {
				cnt--;
			}
		}
		return r;
	}

	@Override
	public void debug4() {
		H.compare(68040, this.evaluate(
				"(let x0 4 x1 -2 x2 3 x3 -5 x4 -3 x5 -1 x6 3 x7 -2 x8 4 x9 -5 (mult x2 (mult (let x0 -3 x4 -2 x8 4 (mult (let x0 -2 x6 4 (add x5 x2)) x3)) (mult (mult -7 (mult -9 (let x0 -2 x7 3 (add -10 x0)))) x6))))"));
		H.compare(-2, this.evaluate("(let x -2 y x y)"));
		H.compare(6, this.evaluate("(let x 2 (add (let x 3 (let x 4 x)) x))"));
		H.compare(6, this.evaluate("(add 2 4)"));
		H.compare(5, this.evaluate("(let x 1 y 2 x (add x y) (add x y))"));
		H.compare(2, this.evaluate("(let x 3 x 2 x)"));
		H.compare(2, this.evaluate("(let x 2 y (mult x (let x 3 y 4 (add x y))) x)"));
		H.compare(14, this.evaluate("(let x 2 (mult x (let x 3 y 4 (add x y))))"));
//		H.compare(14, this.evaluate("(let xx 21 yx 32 x)"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
